package leetcode.primary;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class T40 {
    List<List<Integer>> ans;
    int tail;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);        //预排序
        tail = candidates.length;
        ans = new ArrayList<>();
        dfs(candidates,target,0,0,new ArrayList<>());
        for (int i=1;i<tail;i++){
            if (candidates[i]!=candidates[i-1] ){
                dfs(candidates,target,0,i,new ArrayList<>());
            }
        }
        return ans;
    }

    public void dfs(int[] can,int target,int temp,int i,List<Integer> list){
        if (target <can[i]){
            tail = i;
            return;
        }
        if (target<can[i]+temp){
            return;
        }
        if (can[i]+temp<=target){
            list.add(can[i]);
            if (can[i]+temp==target){
                List<Integer> list1 = new ArrayList<>(list);
                ans.add(list1);

            }
            for (int j=i+1;j<tail;j++){
                if (j>i+1 && can[j]==can[j-1]){         //剪枝
                    continue;
                }
                dfs(can,target,can[i]+temp,j,list);
            }
            list.remove(list.size()-1);
        }
    }
    public boolean Contain(List<Integer> list){         //判断答案list是否包含该数组
        for (List<Integer> temp:ans){
            if (equals(temp,list)){
                return true;
            }
        }
        return false;
    }
    public boolean equals(List<Integer> temp, List<Integer> list){          //判定两个数组是否相同
        if (temp.size()!=list.size()){
            return false;
        }
        for (int i=0;i<temp.size();i++){
            if (temp.get(i)!=list.get(i)){
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        T40 test = new T40();
        List<List<Integer>> list = test.combinationSum2(new int[]{2,5,2,1,2},5);
        for (int i=0;i<list.size();i++){
            List<Integer> li = list.get(i);
            System.out.print("第"+i+"组：");
            for (int j = 0;j< li.size();j++){

                System.out.print(li.get(j)+" ");
            }
            System.out.println();
        }
    }
}
